class Solution {
public:
    const int inf = INT_MAX / 2;                                    
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        vector<vector<vector<int>>> dp(m+1,vector<vector<int>>(target+1,vector<int>(n+1)));
        
         for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][0][j] = inf;
            }
        }
    
        for(int i = 1;i <= m;i++){
            int color = houses[i-1];
            for(int j = 1; j <= target;j++){
                for(int k = 1;k <= n;k++){
                    dp[i][j][k] = inf;
                    if(j > i) continue;
                    
                    if(color != 0){
                        if(k == color){
                            for(int p = 1;p <= n;p++){
                                if(p != k){
                                    dp[i][j][k] = min(dp[i-1][j-1][p],dp[i][j][k]);
                                }
                            }
                            dp[i][j][k] = min(dp[i][j][k],dp[i-1][j][k]);
                        }
                    }else{
                     
                        int c = cost[i-1][k-1];
                        for(int p = 1;p <= n;p++){
                            if(p != k){
                                dp[i][j][k] = min(dp[i][j][k],dp[i-1][j-1][p]);
                            }
                        }
                        dp[i][j][k] = min(dp[i][j][k],dp[i-1][j][k])+c;
                    }
                }
            }
        }
        int ret = INT_MAX;
        for(int k = 1;k <= n;k++){
            ret = min(dp[m][target][k],ret);
        }
        return ret >= inf ? -1 : ret;
    }
};
